
// ToolsLib Project

/* ToolsLib library for RusRoute firewall and other projects of
 * Andrey A. Moiseenko / IE Moiseenko A.A. (Russia)
 * e-mail: support@maasoftware.ru, maa2002@mail.ru
 * web: http://maasoftware.ru, http://maasoftware.com, http://maasoft.ru, http://maasoft.org
 * Author's full name: Andrey Alekseevitch Moiseenko
 * (russian name: Моисеенко Андрей Алексеевич)
 */

// ToolsLib/a_trie.h

/* Copyright (C) 2002-2024 Andrey A. Moiseenko (support@maasoftware.ru)
 * All rights reserved.
 *
 * This library contains strings and string's functions implementation.
 * This CMaaString does not throws throws exception out of boundaries.
 * The library implementation written
 * by Andrey A. Moiseenko (support@maasoftware.ru).
 * This library and applications are
 * FREE FOR COMMERCIAL AND NON-COMMERCIAL USE
 * as long as the following conditions are adhered to.
 *
 * Copyright remains Andrey A. Moiseenko, and as such any Copyright notices in
 * the code are not to be removed.  If this code is used in a product,
 * Andrey A. Moiseenko should be given attribution as the author of the parts used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    This product includes software developed by Andrey A. Moiseenko (support@maasoftware.ru)
 *
 * THIS SOFTWARE IS PROVIDED BY ANDREY A. MOISEENKO ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

//#include "perm.h"
//#include "temp.h"


//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>

// Цифровое TRIE дерево v.14
// Author: Andrey Moiseenko (Андрей Моисеенко)
// Copyright (C) 2017 Andrey Moiseenko
// Licensed under GNU GPL v3
// www: http://maasoftware.ru
// e-mail: support@maasoftware.ru
// Can be commented: #define TRIE10_DEBUG
// Tested with compilers:
// g++ version 12.2.0
// Visual Studio 2022

//#define TRIE10_DEBUG
//#define TRIE10_DEBUG2

#ifdef TRIE10_DEBUG
extern bool gbDbgTrie10Nodes; // debug nodes
#endif

//#define TRIE10_OPT_BITMAP

#if 1

template < class Data > class CMaaTrie
{
protected:
    struct Node
    {
        Node* m_Parent; // родительская вершина
        char m_Value[sizeof(Data)]; // значение
        int m_N; // число букв (вершин)
        char* m_Letters; // отсортированные буквы
        Node** m_Nodes; // вершины, соответствующие буквам
#ifdef TRIE10_OPT_BITMAP
        unsigned char m_BitMap[256 / 8];
#endif
        char m_Letter; // буква
        bool m_bValue; // эта вершина - слово, m_Value имеет смысл

        Node(Node* Parent, char Letter) noexcept
            : m_Parent(Parent),
            //m_Value(-1),
            m_N(0),
            m_Letters(nullptr),
            m_Nodes(nullptr),
            m_Letter(Letter),
            m_bValue(false)
        {
#ifdef TRIE10_OPT_BITMAP
            memset(m_BitMap, 0, sizeof(m_BitMap));
#endif
            //memset(m_Value, 0, sizeof(m_Value));
#ifdef __ALLOCATOR_FILL
            memset(m_Value, __ALLOCATOR_FILL_INIT_CHAR, sizeof(m_Value));
#endif
        }

        ~Node()
        {
            for (int i = 0; i < m_N; i++)
            {
                delete m_Nodes[i];
            }
            delete[] m_Letters;
            delete[] m_Nodes;
            if (m_bValue)
            {
                Data* d = (Data*)m_Value;
                d->~Data();
#ifdef __ALLOCATOR_FILL
                memset(m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(m_Value));
#endif
            }
        }

        // Универсальная функция поиска/вставки/поиска следующей/предыдущей позиции по букве
        template <bool bInsert /* = false */ > int Find (char c, int iNextPrev = 0, int* pPosNextPrev = nullptr) noexcept(!bInsert)
        {
            // бинарный поиск позиции символа c, возвращает -1 если символа нет и bInsert == false && iNextPrev == 0
            // bInsert == true - вставка символа c, которого нет
            // iNextPrev > 0 - позиция следующего символа записывается в *pPosNextPrev, c - нет
            // iNextPrev < 0 - позиция предыдущего символа записывается в *pPosNextPrev, c - нет

#ifdef TRIE10_DEBUG
            gbDbgTrie10Nodes&& printf("Find(%c, %s, %d), %d  %d\n", c, bInsert ? "true" : "false", iNextPrev, m_N, m_Value);
#endif
#ifdef TRIE10_OPT_BITMAP
            if (!bInsert && !iNextPrev && !(m_BitMap[((unsigned char)c) / 8] & (1 << (((unsigned char)c) & 0x7))))
            {
                return -1;
            }
#endif

            // бинарный поиск
            int b = 0, e = m_N - 1;
            while (b < e)
            {
                const int m = (b + e) / 2;

                if (m_Letters[m] < c)
                {
                    b = m + 1;
                }
                else
                {
                    e = m;
                }
            }
#ifdef TRIE10_DEBUG
            gbDbgTrie10Nodes&& printf("%d %d / %d\n", b, e, m_N);
#endif
            if (b < m_N)
            {
                if (m_Letters[b] == c)
                {
                    return b;
                }
                if (m_Letters[b] < c && (bInsert || iNextPrev > 0))
                {
                    // корректировка позиции вставки и следующей буквы
                    b++;
                }
                else if (m_Letters[b] > c && (!bInsert && iNextPrev < 0))
                {
                    // корректировка позиции предыдущей буквы
                    b--;
                }
            }
            else if (!bInsert && iNextPrev < 0)
            {
                // m_N == 0 - корректировка позиции предыдущей буквы
                b = -1;
            }
            if constexpr (bInsert)
            {
                // вставка c,nullptr в позицию b

                char* l = nullptr;
                Node** n = nullptr;
                try
                {
                    l = TL_NEW char[m_N + 1];
                    n = TL_NEW Handle[m_N + 1];
                }
                catch (...)
                {
                    delete[] l;
                    throw; // TODO: eat New[] exceptions
                }
                if (!l || !n)
                {
                    delete[] l;
                    delete[] n;
                    return -1;
                }
                memcpy(l, m_Letters, b);
                l[b] = c;
                memcpy(l + b + 1, m_Letters + b, m_N - b);

                memcpy(n, m_Nodes, b * sizeof(Node*));
                n[b] = nullptr;
                memcpy(n + b + 1, m_Nodes + b, (m_N - b) * sizeof(Node*));

                delete[] m_Letters; m_Letters = l;
                delete[] m_Nodes; m_Nodes = n;
                m_N++;
#ifdef TRIE10_OPT_BITMAP
                m_BitMap[((unsigned char)c) / 8] |= (1 << (((unsigned char)c) & 0x7));
#endif
                return b;
            }
            if (iNextPrev)
            {
                // если нет такой позиции, возвращаем -1
                *pPosNextPrev = (iNextPrev < 0 || (iNextPrev > 0 && b < m_N)) ? b : -1;
            }
            return -1; // не найден при обычном поиске
        }

        // Удаление по индексу позиции
        bool Remove(int pos) noexcept
        {
            if (pos >= 0)
            {
#ifdef TRIE10_OPT_BITMAP
                char c = m_Letters[pos];
                m_BitMap[((unsigned char)c) / 8] &= ~(1 << (((unsigned char)c) & 0x7));
#endif
                // обходимся без reallocation, pos < m_N
                memmove(m_Letters + pos, m_Letters + pos + 1, m_N - (pos + 1));
                memmove(m_Nodes + pos, m_Nodes + pos + 1, (m_N - (pos + 1)) * sizeof(Node*));
                m_N--;
                return true;
            }
            return false;
        }

        // Удаление с поиском по букве
        bool Remove(char c) noexcept
        {
            return Remove(Find<false>(c));
        }

        // Поиск первой вершины относительно позиции
        Node* FirstAtPos(int pos) const noexcept
        {
            Node* p = m_Nodes[pos];
            while (!p->m_bValue && p->m_N > 0)
            {
                p = p->m_Nodes[0];
            }
            return p; // p->m_bValue == true по построению
        }

        // Поиск последней вершины относительно позиции
        Node* LastAtPos(int pos) const noexcept
        {
            Node* p = m_Nodes[pos];
            while (p->m_N > 0)
            {
                p = p->m_Nodes[p->m_N - 1];
            }
            return p; // p->m_bValue == true по построению
        }

        // Поиск следующей вершины через родителя
        Node* NextAtTop() const noexcept
        {
            Node* p = (Node*)this;
            while (p)
            {
                const Node* n = p;
                p = p->m_Parent;
                if (!p)
                {
                    break;
                }
                const int pos = p->Find<false>(n->m_Letter);
                if (pos + 1 < p->m_N)
                {
                    return p->FirstAtPos(pos + 1);
                }
            }
            return p;
        }

        // Поиск предыдущей вершины через родителя
        Node* PrevAtTop() const noexcept
        {
            Node* p = (Node*)this;
            while (p)
            {
                const Node* n = p;
                p = p->m_Parent;
                if (!p)
                {
                    break;
                }
                const int pos = p->Find<false>(n->m_Letter);
                if (pos > 0)
                {
                    return p->LastAtPos(pos - 1);
                }
                if (p->m_bValue)
                {
                    break;
                }
            }
            return p;
        }

        // Получение имени ключа
        bool GetKey(char* p, int Size, bool bAdd0 = true, int* pSizeRequired = nullptr, int* pLen = nullptr) const noexcept
        {
            const Node* n = this;
            int len = 0;
            while (n->m_Parent)
            {
                //int pos = n->m_Parent->Find<false>(n); // slow, use when there is no n->m_Letter; pos >= 0 && pos < n->m_Parent->m_N по построению
                if (len < Size)
                {
                    //p[len] = n->m_Parent->m_Letters[pos];
                    p[len] = n->m_Letter;
                }
                len++;
                n = n->m_Parent;
            }
            int SizeRequired = len + (bAdd0 ? 1 : 0);
            if (pSizeRequired)
            {
                *pSizeRequired = SizeRequired;
            }
            if (pLen)
            {
                *pLen = len;
            }
            if (Size < SizeRequired)
            {
                if (Size > 0 && bAdd0)
                {
                    *p = 0;
                }
                return false;
            }
            for (int i = len / 2; i--;)
            {
                const char c = p[i];
                p[i] = p[len - 1 - i];
                p[len - 1 - i] = c;
            }
            if (bAdd0)
            {
                p[len] = 0;
            }
            return true;
        }

        // Получение имени ключа
        CMaaString GetKey() const
        {
            char Buffer[TOOLSLIB_CS_4K];
            CMaaConcatString c(Buffer, sizeof(Buffer));

            const Node* n = this;
            int len = 0;
            while (n->m_Parent)
            {
                c += n->m_Letter;
                len++;
                n = n->m_Parent;
            }
            CMaaString r = c;
            if (r.Length() != len)
            {
                r.Empty();
                return r;
            }
            char* p = r.GetBuffer();
            for (int i = len / 2; i--;)
            {
                char c = p[i];
                p[i] = p[len - 1 - i];
                p[len - 1 - i] = c;
            }
            return r;
        }

    private:
        // Защита копирования
        Node(const Node&);
        Node& operator = (const Node&);
    };

    Node* m_Root;

#ifdef TRIE10_DEBUG
    bool m_bDbg;
#endif

private:
    // Защита копирования
    CMaaTrie(const CMaaTrie&);
    CMaaTrie& operator = (const CMaaTrie&);
public:
    // Тип хандлера для пользователей
    typedef Node* Handle;

    class iterator
    {
        CMaaTrie* m_trie;
        Handle m_Handle;
        bool m_bDirect;
    public:
        iterator(CMaaTrie& t, Handle h, bool dir) noexcept
            : m_trie(&t),
            m_Handle(h),
            m_bDirect(dir)
        {
        }
        iterator(const iterator& That) noexcept
        {
            *this = That;
        }
        ~iterator() noexcept
        {
        }
        iterator& operator = (const iterator& That) noexcept
        {
            m_trie = That.m_trie;
            m_Handle = That.m_Handle;
            m_bDirect = That.m_bDirect;
            return *this;
        }
        void Swap(iterator& That) noexcept
        {
            iterator tmp(*this);
            *this = That;
            That = tmp;
        }
        iterator operator++(int) noexcept
        {
            iterator tmp(*this);
            ++(*this);
            return tmp;
        }
        iterator operator++() noexcept
        {
            m_Handle = m_bDirect ? m_trie->Next(m_Handle) : m_trie->Prev(m_Handle);
            return *this;
        }
        iterator operator--(int) noexcept
        {
            iterator tmp(*this);
            --(*this);
            return tmp;
        }
        iterator operator--() noexcept
        {
            m_Handle = m_bDirect ? m_trie->Prev(m_Handle) : m_trie->Next(m_Handle);
            return *this;
        }
        bool operator==(const iterator& That) const noexcept
        {
            return m_Handle == That.m_Handle && m_trie == That.m_trie && m_bDirect == That.m_bDirect;
        }
        bool operator!=(const iterator& That) const noexcept
        {
            return !(*this == That);
        }
        operator Handle() noexcept
        {
            return m_Handle;
        }
        bool GetKey(char* p, int Size, bool bAdd0 = true, int* pSizeRequired = nullptr, int* pLen = nullptr) const
        {
            return m_trie->GetKey(m_Handle, p, Size, bAdd0, pSizeRequired, pLen);
        }
        CMaaString GetKey() const
        {
            return m_trie->GetKey(m_Handle);
        }
        /*
        const Key & ckey()
        {
            if   (!IsValid())
            {
                throw 1;
            }
            return r->K;
        }
        Key key()
        {
            if   (!IsValid())
            {
                throw 1;
            }
            return r->K;
        }
        */
        Data& rdata() noexcept(std::is_nothrow_move_constructible<Data>::value)
        {
            return m_trie->Value(m_Handle);
        }
        Data data() noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
        {
            return m_trie->GetValue(m_Handle);
        }
        bool Remove(Data* pval = nullptr) noexcept(noexcept(*pval = *pval))
        {
            return m_trie->Remove(m_Handle, pval);
        }
    };

    // Конструктор
    CMaaTrie() noexcept
    {
        m_Root = nullptr;
#ifdef TRIE10_DEBUG
        m_bDbg = false;
#endif
    }

    // Деструктор
    virtual ~CMaaTrie()
    {
        delete m_Root;
    }

    // inline functions
    // Добавить ключ str со значением val
    bool Add(const char* str, const Data& val)
    {
#ifdef TRIE10_DEBUG
        m_bDbg&& printf("Add(%s, %d): ", str, val);
#endif
        return Add(str, (int)strlen(str), val);
    }

    // Удалить ключ str, вернув значение в *pval
    bool Remove(const char* str, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
#ifdef TRIE10_DEBUG
        m_bDbg&& printf("Remove(%s): ", str);
#endif
        return Remove(str, (int)strlen(str), pval);
    }

    // Не рекомендуем в api, упрощённый интерфейс для задания
    Data Find(const char* str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        return Find(str, (int)strlen(str));
    }

    // Не рекомендуем в api, упрощённый интерфейс для задания
    Data Find(const char* str, int len) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        Data v{};// = -1; // возвращаем -1, если слово не найдено
        Find(str, len, &v);
        return v;
    }

    // Рекомендуем в api, более удобная функция
    bool Find(const char* str, Data* pval) const noexcept(noexcept(*pval=*pval))
    {
#ifdef TRIE10_DEBUG
        if (m_bDbg)
        {
            printf("Find(%s): ", str);
            int v{};// = -1;
            pval = pval ? pval : &v;
            bool b = Find(str, (int)strlen(str), pval);
            printf(b ? "%d " : "false ", *pval);
            return b;
        }
#endif
        return Find(str, (int)strlen(str), pval);
    }

    // Поиск последующего слова > str или >= str, если bEqual = true
    Handle FindGQ(const char* str, bool bEqual = false) const noexcept
    {
#ifdef TRIE10_DEBUG
        m_bDbg&& printf("FindGQ(%s, %s): ", str, bEqual ? "true" : "false");
#endif
        return FindGQ(str, (int)strlen(str), bEqual);
    }

    // Поиск предшествующего слова < str или <= str, если bEqual = true
    Handle FindLQ(const char* str, bool bEqual = false) const noexcept
    {
#ifdef TRIE10_DEBUG
        m_bDbg&& printf("FindLQ(%s, %s): ", str, bEqual ? "true" : "false");
#endif
        return FindLQ(str, (int)strlen(str), bEqual);
    }

    // CMaaString - functions
    //////////
    // Добавить ключ str со значением val
    bool AddS(CMaaString str, const Data& val)
    {
        return Add((const char*)str, str.Length(), val);
    }
    // Удалить ключ str, вернув значение в *pval
    bool RemoveS(CMaaString str, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
        return Remove((const char*)str, str.Length(), pval);
    }
    // Не рекомендуем в api, упрощённый интерфейс для задания
    Data FindS(CMaaString str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        return Find((const char*)str, str.Length());
    }
    // Рекомендуем в api, более удобная функция
    bool FindS(CMaaString str, Data* pval) const noexcept(noexcept(*pval=*pval))
    {
        return Find((const char*)str, str.Length(), pval);
    }
    // Поиск последующего слова > str или >= str, если bEqual = true
    Handle FindGQS(CMaaString str, bool bEqual = false) const noexcept
    {
        return FindGQ((const char*)str, str.Length(), bEqual);
    }
    // Поиск предшествующего слова < str или <= str, если bEqual = true
    Handle FindLQS(CMaaString str, bool bEqual = false) const noexcept
    {
        return FindLQ((const char*)str, str.Length(), bEqual);
    }
    //////////

    // Поиск первого слова
    Handle First() const noexcept
    {
        Node* x = m_Root;
        if (x && x->m_bValue == false)
        {
            x = x->FirstAtPos(0);
        }
        return x;
    }

    // Поиск последнего слова
    Handle Last() const noexcept
    {
        Node* x = m_Root;
        if (x && x->m_N > 0)
        {
            x = x->LastAtPos(x->m_N - 1);
        }
        return x;
    }

    iterator begin() noexcept
    {
        iterator it(*this, First(), true);
        return it;
    }

    iterator end() noexcept
    {
        iterator it(*this, nullptr, true);
        return it;
    }

    iterator rbegin() noexcept
    {
        iterator it(*this, Last(), false);
        return it;
    }

    iterator rend() noexcept
    {
        iterator it(*this, nullptr, false);
        return it;
    }

    iterator it(Handle h, bool dir = true) noexcept
    {
        iterator it(*this, h, dir);
        return it;
    }

    // Не рекомендуем в api, для задания
    // Ссылка на значение по хандлеру
    Data& Value(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value)
    {
        // не рекомендуется
        static Data v0{};
        return h ? *(Data*)h->m_Value : (v0);// = -1);
    }

    // Не рекомендуем в api, для задания
    // Получение значение по хандлеру
    Data GetValue(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        return Value(h);
    }

    // Рекомендуем в api, для задания
    // Получение значения по хандлеру, может вернуть false если h не слово
    bool GetValue(Handle h, Data* pval) noexcept(noexcept(*pval=*pval))
    {
        if (h && h->m_bValue)
        {
            if (pval)
            {
                *pval = *(Data*)h->m_Value;
            }
            return true;
        }
        return false;
    }

    // Установка значения по хандлеру, может вернуть false если h не слово
    bool SetValue(Handle h, const Data& v) noexcept(std::is_nothrow_move_assignable<Data>::value)
    {
        if (h && h->m_bValue)
        {
            *(Data*)h->m_Value = v;
            return true;
        }
        return false;
    }

    // Поиск узла по ключу, ключ может быть не словом
    Handle FindHandle(const char* str) const noexcept
    {
        return FindHandle(str, (int)strlen(str));
    }

    // Получить ключ без '\0' в конце
    bool GetKey(Handle h, char* p, int Size, int* pSizeRequired, int* pLen) const noexcept
    {
        return GetKey(h, p, Size, false, pSizeRequired, pLen);
    }

#ifdef TRIE10_DEBUG
    void SetDbg(bool bSet) noexcept
    {
        m_bDbg = bSet;
    }
#else
    void SetDbg(bool) noexcept
    {
    }
#endif

    // Основные функции для не null-terminated строк

    // Добавить слово str длиной len со значением val
    bool Add(const char* str, int len, const Data& val)
    {
        if (/*val < 0 ||*/ len <= 0)
        {
            return false; // недопустимое значение value или len
        }
        if (!m_Root)
        {
            m_Root = TL_NEW Node(nullptr, 0);
            if (!m_Root)
            {
                return false;
            }
        }
        Node* p = m_Root;
        int i = 0, pos0 = -1;
        try
        {
            for (; i < len; i++)
            {
                const char c = str[i];
                int pos = p->Find<true>(c);
                if (pos < 0)
                {
                    break; // New [] error
                }
                if (!p->m_Nodes[pos])
                {
                    pos0 = pos; // запоминаем позицию буквы с нулевым указателем
                    p->m_Nodes[pos] = TL_NEW Node(p, c);
                    if (!p->m_Nodes[pos])
                    {
                        //p->Remove(pos); // удалим [pos0==pos] вне цикла
                        break;
                    }
                    pos0 = -1; // забываем позицию
                }
                p = p->m_Nodes[pos];
            }
            if (i >= len)
            {
                Data* d = (Data*)p->m_Value;
                if (!p->m_bValue)
                {
#ifdef __ALLOCATOR_FILL
                    memset(p->m_Value, __ALLOCATOR_FILL_ALLOC_CHAR, sizeof(p->m_Value));
#endif
                    new_(d, Data(val));
                }
                else
                {
                    *d = val;
                }
                p->m_bValue = true;
                //return true;
            }
        }
        catch (...)
        {
            // New [] error
            if (pos0 >= 0)
            {
                p->Remove(pos0); // более быстро, чем p->Remove(nullptr);
            }
            RemoveUnused(p);
            throw;
        }
        if (i < len)
        {
            // New [] error
            if (pos0 >= 0)
            {
                p->Remove(pos0); // более быстро, чем p->Remove(nullptr);
            }
            RemoveUnused(p);
            return false;
        }
        //p->m_Value = val;
        //p->m_bValue = true;
        return true;
    }

    // Удалить слово str длиной len, вернув значение в *pval
    bool Remove(const char* str, int len, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
        Node* p = FindHandle(str, len);
        return Remove(p, pval);
    }

    // Удалить слово вершины p, вернув значение в *pval
    bool Remove(Node* p, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
        if (p && p->m_bValue)
        {
            Data* d = (Data*)p->m_Value;
            if (pval)
            {
                *pval = *d;
            }
            d->~Data();
#ifdef __ALLOCATOR_FILL
            memset(p->m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(p->m_Value));
#endif
            p->m_bValue = false;
            RemoveUnused(p);
            return true;
        }
        return false;
    }

    // Поиск вершины по ключу, может вернуть вершину - не слово
    Handle FindHandle(const char* str, int len) const noexcept
    {
        Node* p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const char c = str[i];
            int pos = p->Find<false>(c);
            if (pos < 0)
            {
                p = nullptr;
                break;
            }
            p = p->m_Nodes[pos];
        }
        return p;
    }

    // Поиск слова, возврат значения в *pval, return true on success
    bool Find(const char* str, int len, Data* pval) const noexcept(noexcept(*pval=*pval))
    {
        Node* x = FindHandle(str, len);
        if (x && x->m_bValue == false)
        {
            // не слово
            return false;
        }
        if (x && pval)
        {
            *pval = *(Data*)x->m_Value;
        }
        return x ? true : false;
    }

    // Поиск последующего слова > str или >= str, если bEqual = true
    Handle FindGQ(const char* str, int len, bool bEqual = false) const noexcept
    {
        Node* p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const char c = str[i];
            int pos_next = -1; // позиция для следующего символа, если c не найден
            int pos = p->Find<false>(c, 1, &pos_next);
#ifdef TRIE10_DEBUG2
            m_bDbg&& printf("%d\n", pos);
#endif
            if (pos < 0)
            {
#ifdef TRIE10_DEBUG2
                m_bDbg&& printf("%d\n", pos_next);
#endif
                if (pos_next >= 0)
                {
                    return p->FirstAtPos(pos_next);
                }
                return p->NextAtTop();
            }
            p = p->m_Nodes[pos];
        }
        if (p && (!bEqual || p->m_bValue == false))
        {
            p = Next(p);
        }
        return p;
    }

    // Поиск предшествующего слова < str или <= str, если bEqual = true
    Handle FindLQ(const char* str, int len, bool bEqual = false) const noexcept
    {
        Node* p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const char c = str[i];
            int pos_prev = -1; // позиция для предыдущего символа, если c не найден
            int pos = p->Find<false>(c, -1, &pos_prev);
#ifdef TRIE10_DEBUG2
            m_bDbg&& printf("%d\n", pos);
#endif
            if (pos < 0)
            {
#ifdef TRIE10_DEBUG2
                m_bDbg&& printf("%d\n", pos_prev);
#endif
                if (pos_prev >= 0)
                {
                    return p->LastAtPos(pos_prev);
                }
                return p->PrevAtTop();
            }
            p = p->m_Nodes[pos];
        }
        if (p && (!bEqual || p->m_bValue == false))
        {
            p = Prev(p);
        }
        return p;
    }

    // Определение максимального пути (слова/части слова)
    Handle MaxPath(const char* str, int len, int* plen, int* pincompleteLen = nullptr, Data* pval = nullptr) const noexcept(noexcept(*pval=*pval))
    {
        int rlen = 0, inclen = 0;
        Handle r = nullptr;

        Node* p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const char c = str[i];
            int pos = p->Find<false>(c);
            if (pos < 0)
            {
                p = nullptr;
                break;
            }
            p = p->m_Nodes[pos];
            inclen++;
            if (p->m_bValue)
            {
                rlen = inclen;
                r = p;
            }
        }
        if (plen)
        {
            *plen = rlen;
        }
        if (pincompleteLen)
        {
            *pincompleteLen = inclen;
        }
        if (r && pval)
        {
            *pval = *(Data*)r->m_Value;
        }
        return r;
    }

    // Определение первого пути (слова/части слова)
    Handle FirstPath(const char* str, int len, int* plen, int* pincompleteLen = nullptr, Data* pval = nullptr) const noexcept(noexcept(*pval=*pval))
    {
        int rlen = 0, inclen = 0;
        Handle r = nullptr;

        Node* p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            char c = str[i];
            int pos = p->Find<false>(c);
            if (pos < 0)
            {
                p = nullptr;
                break;
            }
            p = p->m_Nodes[pos];
            inclen++;
            if (p->m_bValue)
            {
                rlen = inclen;
                r = p;
                break; // первое существующее слово
            }
        }
        if (plen)
        {
            *plen = rlen;
        }
        if (pincompleteLen)
        {
            *pincompleteLen = inclen;
        }
        if (r && pval)
        {
            *pval = *(Data*)r->m_Value;
        }
        return r;
    }

    // Следующее слово
    Handle Next(Handle p) const noexcept
    {
        if (p)
        {
            return p->m_N > 0 ? p->FirstAtPos(0) : p->NextAtTop();
        }
        return nullptr;
    }

    // Предшествующее слово
    Handle Prev(Handle p) const noexcept
    {
        if (p)
        {
            return p->PrevAtTop();
        }
        return nullptr;
    }

    // Удалить вершины-не слова без дочерних, поднимаясь вверх
    Node* RemoveUnused(Node* p) noexcept
    {
        while (p && p->m_bValue == false && p->m_N == 0)
        {
            // эту вершину можно удалить
            Node* x = p;
            p = p->m_Parent;
            if (!p)
            {
                // делаем дерево пустым
                m_Root = nullptr;
            }
            else
            {
                p->Remove(x->m_Letter); // более быстро, чем p->Remove(x);
            }
            delete x;
        }
        return p;
    }

    // Тестовая печать дерева, вызывается без параметров
    void Print(char* str = nullptr, Node* x = nullptr, int pos = 0) const;
    // Тестовая печать слов дерева, вызывается без параметров
    int PrintWords(char* str = nullptr, Node* x = nullptr, int pos = 0) const;

    // Получить имя ключа, универсально - с/без '\0' в конце
    bool GetKey(Handle h, char* p, int Size, bool bAdd0 = true, int* pSizeRequired = nullptr, int* pLen = nullptr) const noexcept
    {
        if (h)
        {
            return h->GetKey(p, Size, bAdd0, pSizeRequired, pLen);
        }
        if (Size > 0 && bAdd0)
        {
            *p = 0;
        }
        if (pSizeRequired)
        {
            *pSizeRequired = 0; // or 1
        }
        if (pLen)
        {
            *pLen = 0;
        }
        return false;
    }

    // Получить имя ключа в CMaaString
    CMaaString GetKey(Handle h) const
    {
        if (h)
        {
            return h->GetKey();
        }
        CMaaString tmp;
        return tmp;
    }
};

#endif

#if 2

template < class Data, char ch0 = '\0', int AlphabetSize = 256 > class CMaaTrie2
{
protected:
    struct Node
    {
        Node * m_Parent; // родительская вершина
        char m_Value[sizeof(Data)]; // значение
        Node * m_Nodes[AlphabetSize]; // вершины, соответствующие буквам
        char m_Letter; // буква
        bool m_bValue; // эта вершина - слово, m_Value имеет смысл

        Node(Node * Parent, char Letter) noexcept
        :   m_Parent(Parent),
            m_Letter(Letter),
            m_bValue(false)
        {
            memset(m_Nodes, 0, sizeof(m_Nodes));
#ifdef __ALLOCATOR_FILL
            memset(m_Value, __ALLOCATOR_FILL_INIT_CHAR, sizeof(m_Value));
#endif
        }

        ~Node() noexcept
        {
            for (int i = 0; i < AlphabetSize; i++)
            {
                delete m_Nodes[i];
            }
            if  (m_bValue)
            {
                Data * d = (Data *)m_Value;
                d->~Data();
#ifdef __ALLOCATOR_FILL
                memset(m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(m_Value));
#endif
            }
        }

        // Удаление с поиском по букве
        /*
        bool Remove(char c)
        {
            return Remove(Find<false>(c));
        }
        */

        // slow
        int GetCount() const noexcept // slow
        {
            int N = 0;
            for (int idx = 0; idx < AlphabetSize; idx++)
            {
                if (m_Nodes[idx])
                {
                    N++;
                }
            }
            return N;
        }

        Node* FindN1(int idx) const noexcept
        {
            while (++idx < AlphabetSize)
            {
                if (m_Nodes[idx])
                {
                    return m_Nodes[idx];
                }
            }
            return nullptr;
        }

        Node* FindP1(int idx) const noexcept
        {
            while (--idx >= 0)
            {
                if (m_Nodes[idx])
                {
                    return m_Nodes[idx];
                }
            }
            return nullptr;
        }

        // Поиск первой вершины относительно позиции
        static Node* FirstAtPos(Node* p) noexcept
        {
            while (!p->m_bValue)
            {
                Node* n = p->FindN1(-1);
                if (!n)
                {
                    break;
                }
                p = n;
            }
            return p; // p->m_bValue == true по построению
        }

        // Поиск первой вершины относительно позиции
        Node * FirstAtPos(int pos) const noexcept
        {
            return FirstAtPos(m_Nodes[pos]);
        }

        // Поиск последней вершины относительно позиции
        static Node* LastAtPos(Node* p) noexcept
        {
            while (1)
            {
                Node* n = p->FindP1(AlphabetSize);
                if (!n)
                {
                    break;
                }
                p = n;
            }
            return p; // p->m_bValue == true по построению
        }

        // Поиск последней вершины относительно позиции
        Node * LastAtPos(int pos) const noexcept
        {
            return LastAtPos(m_Nodes[pos]);
        }

        // Поиск следующей вершины через родителя
        Node * NextAtTop() const noexcept
        {
            Node * p = (Node *)this;
            while(p)
            {
                const int pos = (int)(unsigned char)p->m_Letter;
                p = p->m_Parent;
                if  (!p)
                {
                    break;
                }
                Node* n = p->FindN1(pos);
                if (n)
                {
                    return FirstAtPos(n);
                }
            }
            return p;
        }

        // Поиск предыдущей вершины через родителя
        Node* PrevAtTop() const noexcept
        {
            Node* p = (Node*)this;
            while (p)
            {
                const int pos = (int)(unsigned char)p->m_Letter;
                p = p->m_Parent;
                if (!p)
                {
                    break;
                }
                Node* n = p->FindP1(pos);
                if (n)
                {
                    return LastAtPos(n);
                }
                if (p->m_bValue)
                {
                    break;
                }
            }
            return p;
        }

        // Получение имени ключа
        bool GetKey(char *p, int Size, bool bAdd0 = true, int *pSizeRequired = nullptr, int *pLen = nullptr) const noexcept
        {
            const Node * n = this;
            int len = 0;
            while(n->m_Parent)
            {
                //int pos = n->m_Parent->Find(n); // slow, use when there is no n->m_Letter; pos >= 0 && pos < n->m_Parent->m_N по построению
                if  (len < Size)
                {
                    //p[len] = n->m_Parent->m_Letters[pos];
                    p[len] = n->m_Letter + ch0;
                }
                len++;
                n = n->m_Parent;
            }
            int SizeRequired = len + (bAdd0 ? 1 : 0);
            if  (pSizeRequired)
            {
                *pSizeRequired = SizeRequired;
            }
            if  (pLen)
            {
                *pLen = len;
            }
            if  (Size < SizeRequired)
            {
                if  (Size > 0 && bAdd0)
                {
                    *p = 0;
                }
                return false;
            }
            for (int i = len / 2; i--;)
            {
                const char c = p[i];
                p[i] = p[len - 1 - i];
                p[len - 1 - i] = c;
            }
            if  (bAdd0)
            {
                p[len] = 0;
            }
            return true;
        }

        // Получение имени ключа
        CMaaString GetKey() const
        {
            char Buffer[TOOLSLIB_CS_4K];
            CMaaConcatString c(Buffer, sizeof(Buffer));

            const Node * n = this;
            int len = 0;
            while(n->m_Parent)
            {
                c += (char)(n->m_Letter + ch0);
                len++;
                n = n->m_Parent;
            }
            CMaaString r = c;
            if  (r.Length() != len)
            {
                r.Empty();
                return r;
            }
            char *p = r.GetBuffer();
            for (int i = len / 2; i--;)
            {
                char c = p[i];
                p[i] = p[len - 1 - i];
                p[len - 1 - i] = c;
            }
            return r;
        }

    private:
        // Защита копирования
        Node(const Node &);
        Node & operator = (const Node &);
    };

    Node * m_Root;

private:
    // Защита копирования
    CMaaTrie2(const CMaaTrie2 &);
    CMaaTrie2 & operator = (const CMaaTrie2 &);
public:
    // Тип хандлера для пользователей
    typedef Node * Handle;

    class iterator
    {
        CMaaTrie2 * m_trie;
        Handle m_Handle;
        bool m_bDirect;
    public:
        iterator(CMaaTrie2 &t, Handle h, bool dir) noexcept
        :   m_trie(&t),
            m_Handle(h),
            m_bDirect(dir)
        {
        }
        iterator(const iterator &That) noexcept
        {
            *this = That;
        }
        ~iterator() noexcept
        {
        }
        iterator & operator = (const iterator &That) noexcept
        {
            m_trie = That.m_trie;
            m_Handle = That.m_Handle;
            m_bDirect = That.m_bDirect;
            return *this;
        }
        void Swap(iterator &That) noexcept
        {
            iterator tmp(*this);
            *this = That;
            That = tmp;
        }
        iterator operator++(int) noexcept
        {
            iterator tmp(*this);
            ++(*this);
            return tmp;
        }
        iterator operator++() noexcept
        {
            m_Handle = m_bDirect ? m_trie->Next(m_Handle) : m_trie->Prev(m_Handle);
            return *this;
        }
        iterator operator--(int) noexcept
        {
            iterator tmp(*this);
            --(*this);
            return tmp;
        }
        iterator operator--() noexcept
        {
            m_Handle = m_bDirect ? m_trie->Prev(m_Handle) : m_trie->Next(m_Handle);
            return *this;
        }
        bool operator==(const iterator &That) const noexcept
        {
            return m_Handle == That.m_Handle && m_trie == That.m_trie && m_bDirect == That.m_bDirect;
        }
        bool operator!=(const iterator &That) const noexcept
        {
            return !(*this == That);
        }
        operator Handle() noexcept
        {
            return m_Handle;
        }
        bool GetKey(char *p, int Size, bool bAdd0 = true, int *pSizeRequired = nullptr, int *pLen = nullptr) const noexcept
        {
            return m_trie->GetKey(m_Handle, p, Size, bAdd0, pSizeRequired, pLen);
        }
        CMaaString GetKey() const
        {
            return m_trie->GetKey(m_Handle);
        }
        /*
        const Key & ckey()
        {
            if   (!IsValid())
            {
                throw 1;
            }
            return r->K;
        }
        Key key()
        {
            if   (!IsValid())
            {
                throw 1;
            }
            return r->K;
        }
        */
        Data & rdata() noexcept(std::is_nothrow_move_constructible<Data>::value)
        {
            return m_trie->Value(m_Handle);
        }
        Data data() noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
        {
            return m_trie->GetValue(m_Handle);
        }
        bool Remove(Data * pval = nullptr) noexcept(noexcept(*pval=*pval))
        {
            return m_trie->Remove(m_Handle, pval);
        }
    };

    // Конструктор
    CMaaTrie2() noexcept
    {
        m_Root = nullptr;
    }

    // Деструктор
    virtual ~CMaaTrie2()
    {
        delete m_Root;
    }

    // inline functions
    // Добавить ключ str со значением val
    bool Add(const char * str, const Data &val)
    {
        return Add(str, (int)strlen(str), val);
    }

    // Удалить ключ str, вернув значение в *pval
    bool Remove(const char * str, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
        return Remove(str, (int)strlen(str), pval);
    }

    // Не рекомендуем в api, упрощённый интерфейс для задания
    Data Find(const char * str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        return Find(str, (int)strlen(str));
    }

    // Не рекомендуем в api, упрощённый интерфейс для задания
    Data Find(const char * str, int len) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        Data v{};// = -1; // возвращаем -1, если слово не найдено
        Find(str, len, &v);
        return v;
    }

    // Рекомендуем в api, более удобная функция
    bool Find(const char * str, Data * pval) const noexcept(noexcept(*pval=*pval))
    {
        return Find(str, (int)strlen(str), pval);
    }

    // Поиск последующего слова > str или >= str, если bEqual = true
    Handle FindGQ(const char * str, bool bEqual = false) const noexcept
    {
        return FindGQ(str, (int)strlen(str), bEqual);
    }

    // Поиск предшествующего слова < str или <= str, если bEqual = true
    Handle FindLQ(const char * str, bool bEqual = false) const noexcept
    {
        return FindLQ(str, (int)strlen(str), bEqual);
    }

    // CMaaString - functions
    //////////
    // Добавить ключ str со значением val
    bool AddS(CMaaString str, const Data &val) noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        return Add((const char *)str, str.Length(), val);
    }
    // Удалить ключ str, вернув значение в *pval
    bool RemoveS(CMaaString str, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
        return Remove((const char *)str, str.Length(), pval);
    }
    // Не рекомендуем в api, упрощённый интерфейс для задания
    Data FindS(CMaaString str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        return Find((const char *)str, str.Length());
    }
    // Рекомендуем в api, более удобная функция
    bool FindS(CMaaString str, Data * pval) const noexcept(noexcept(*pval=*pval))
    {
        return Find((const char *)str, str.Length(), pval);
    }
    // Поиск последующего слова > str или >= str, если bEqual = true
    Handle FindGQS(CMaaString str, bool bEqual = false) const noexcept
    {
        return FindGQ((const char *)str, str.Length(), bEqual);
    }
    // Поиск предшествующего слова < str или <= str, если bEqual = true
    Handle FindLQS(CMaaString str, bool bEqual = false) const noexcept
    {
        return FindLQ((const char *)str, str.Length(), bEqual);
    }
    //////////

    // Поиск первого слова
    Handle First() const noexcept
    {
        Node * x = m_Root;
        if  (x && x->m_bValue == false)
        {
            x = x->FindN1(-1);
            x = Node::FirstAtPos(x);
        }
        return x;
    }

    // Поиск последнего слова
    Handle Last() const noexcept
    {
        Node * x = m_Root;
        if  (x)
        {
            x = x->FindP1(AlphabetSize);
            x = Node::LastAtPos(x);
        }
        return x;
    }

    iterator begin() noexcept
    {
        iterator it(*this, First(), true);
        return it;
    }

    iterator end() noexcept
    {
        iterator it(*this, nullptr, true);
        return it;
    }

    iterator rbegin() noexcept
    {
        iterator it(*this, Last(), false);
        return it;
    }

    iterator rend() noexcept
    {
        iterator it(*this, nullptr, false);
        return it;
    }

    iterator it(Handle h, bool dir = true) noexcept
    {
        iterator it(*this, h, dir);
        return it;
    }

    // Не рекомендуем в api, для задания
    // Ссылка на значение по хандлеру
    Data & Value(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value)
    {
        // не рекомендуется
        static Data v0{};
        return h ? *(Data *)h->m_Value : (v0);// = -1);
    }

    // Не рекомендуем в api, для задания
    // Получение значение по хандлеру
    Data GetValue(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
    {
        return Value(h);
    }

    // Рекомендуем в api, для задания
    // Получение значения по хандлеру, может вернуть false если h не слово
    bool GetValue(Handle h, Data *pval) noexcept(noexcept(*pval=*pval))
    {
        if  (h && h->m_bValue)
        {
            if  (pval)
            {
                *pval = *(Data *)h->m_Value;
            }
            return true;
        }
        return false;
    }

    // Установка значения по хандлеру, может вернуть false если h не слово
    bool SetValue(Handle h, const Data &v) noexcept(std::is_nothrow_move_assignable<Data>::value)
    {
        if  (h && h->m_bValue)
        {
            *(Data *)h->m_Value = v;
            return true;
        }
        return false;
    }

    // Поиск узла по ключу, ключ может быть не словом
    Handle FindHandle(const char * str) const noexcept
    {
        return FindHandle(str, (int)strlen(str));
    }

    // Получить ключ без '\0' в конце
    bool GetKey(Handle h, char *p, int Size, int *pSizeRequired, int *pLen) const noexcept
    {
        return GetKey(h, p, Size, false, pSizeRequired, pLen);
    }

    // Основные функции для не null-terminated строк

    // Добавить слово str длиной len со значением val
    bool Add(const char * str, int len, const Data &val)
    {
        if  (/*val < 0 ||*/ len <= 0)
        {
            return false; // недопустимое значение value или len
        }
        if  (!m_Root)
        {
            m_Root = TL_NEW Node(nullptr, '\0');
            if  (!m_Root)
            {
                return false;
            }
        }
        Node * p = m_Root;
        int i = 0;
        try
        {
            for (; i < len; i++)
            {
                const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
                if (c < 0 || c >= AlphabetSize)
                {
                    // break;
                    throw 1;
                }
                Node* n = p->m_Nodes[c];
                if (!n)
                {
                    n = p->m_Nodes[c] = TL_NEW Node(p, (char)c);
                    if (!n)
                    {
                        // break;
                        throw 1;
                    }
                }
                p = n;
            }
            if  (i >= len)
            {
                Data * d = (Data *)p->m_Value;
                if  (!p->m_bValue)
                {
#ifdef __ALLOCATOR_FILL
                    memset(p->m_Value, __ALLOCATOR_FILL_ALLOC_CHAR, sizeof(p->m_Value));
#endif
                    new_(d, Data(val));
                }
                else
                {
                    *d = val;
                }
                p->m_bValue = true;
                return true;
            }
        }
        catch(...)
        {
            RemoveUnused(p);
            throw;
        }
        if  (i < len)
        {
            RemoveUnused(p);
            return false;
        }
        return true;
    }

    // Удалить слово str длиной len, вернув значение в *pval
    bool Remove(const char * str, int len, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
        Node * p = FindHandle(str, len);
        return Remove(p, pval);
    }

    // Удалить слово вершины p, вернув значение в *pval
    bool Remove(Node * p, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
    {
        if  (p && p->m_bValue)
        {
            Data * d = (Data *)p->m_Value;
            if  (pval)
            {
                *pval = *d;
            }
            d->~Data();
#ifdef __ALLOCATOR_FILL
            memset(p->m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(p->m_Value));
#endif
            p->m_bValue = false;
            RemoveUnused(p);
            return true;
        }
        return false;
    }

    // Поиск вершины по ключу, может вернуть вершину - не слово
    Handle FindHandle(const char * str, int len) const noexcept
    {
        Node * p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
            if (c < 0 || c >= AlphabetSize)
            {
                return nullptr;
            }
            p = p->m_Nodes[c];
        }
        return p;
    }

    // Поиск слова, возврат значения в *pval, return true on success
    bool Find(const char * str, int len, Data *pval) const noexcept(noexcept(*pval=*pval))
    {
        Node * x = FindHandle(str, len);
        if  (x && x->m_bValue == false)
        {
            // не слово
            return false;
        }
        if  (x && pval)
        {
            *pval = *(Data *)x->m_Value;
        }
        return x ? true : false;
    }

    // Поиск последующего слова > str или >= str, если bEqual = true
    Handle FindGQ(const char * str, int len, bool bEqual = false) const noexcept
    {
        Node * p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
            if ((c < 0 || c >= AlphabetSize) || !p->m_Nodes[c])
            {
                Node* n = c < 0 ? p->FindN1(-1) : c >= AlphabetSize ? nullptr : p->FindN1(c);
                if  (n)
                {
                    return Node::FirstAtPos(n);
                }
                return p->NextAtTop();
            }
            p = p->m_Nodes[c];
        }
        if  (p && (!bEqual || p->m_bValue == false))
        {
            p = Next(p);
        }
        return p;
    }

    // Поиск предшествующего слова < str или <= str, если bEqual = true
    Handle FindLQ(const char * str, int len, bool bEqual = false) const noexcept
    {
        Node * p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
            if ((c < 0 || c >= AlphabetSize) || !p->m_Nodes[c])
            {
                Node* n = c >= AlphabetSize ? p->FindP1(AlphabetSize) : c < 0 ? nullptr : p->FindP1(c);
                if (n)
                {
                    return Node::LastAtPos(n);
                }
                return p->PrevAtTop();
            }
            p = p->m_Nodes[c];
        }
        if  (p && (!bEqual || p->m_bValue == false))
        {
            p = Prev(p);
        }
        return p;
    }

    // Определение максимального пути (слова/части слова)
    Handle MaxPath(const char * str, int len, int *plen, int *pincompleteLen = nullptr, Data *pval = nullptr) const noexcept(noexcept(*pval=*pval))
    {
        int rlen = 0, inclen = 0;
        Handle r = nullptr;

        Node * p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
            if (c < 0 || c >= AlphabetSize)
            {
                break;
                // throw 1;
            }
            p = p->m_Nodes[c];
            if  (!p)
            {
                break;
            }
            inclen++;
            if  (p->m_bValue)
            {
                rlen = inclen;
                r = p;
            }
        }
        if  (plen)
        {
            *plen = rlen;
        }
        if  (pincompleteLen)
        {
            *pincompleteLen = inclen;
        }
        if  (r && pval)
        {
            *pval = *(Data *)r->m_Value;
        }
        return r;
    }

    // Определение первого пути (слова/части слова)
    Handle FirstPath(const char * str, int len, int *plen, int *pincompleteLen = nullptr, Data *pval = nullptr) const noexcept(noexcept(*pval=*pval))
    {
        int rlen = 0, inclen = 0;
        Handle r = nullptr;

        Node * p = m_Root;
        for (int i = 0; i < len && p; i++)
        {
            const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
            if (c < 0 || c >= AlphabetSize)
            {
                break;
                //throw 1;
            }
            p = p->m_Nodes[c];
            if  (!p)
            {
                break;
            }
            inclen++;
            if  (p->m_bValue)
            {
                rlen = inclen;
                r = p;
                break; // первое существующее слово
            }
        }
        if  (plen)
        {
            *plen = rlen;
        }
        if  (pincompleteLen)
        {
            *pincompleteLen = inclen;
        }
        if  (r && pval)
        {
            *pval = *(Data *)r->m_Value;
        }
        return r;
    }

    // Следующее слово
    Handle Next(Handle p) const noexcept
    {
        if (p)
        {
            Node* n = p->FindN1(-1);
            if (n)
            {
                return Node::FirstAtPos(n);
            }
            return p->NextAtTop();
        }
        return nullptr;
    }

    // Предшествующее слово
    Handle Prev(Handle p) const noexcept
    {
        if  (p)
        {
            return p->PrevAtTop();
        }
        return nullptr;
    }

    // Удалить вершины-не слова без дочерних, поднимаясь вверх
    Node * RemoveUnused(Node * p) noexcept
    {
        while (p && p->m_bValue == false)
        {
            if (p->FindN1(-1))
            {
                return p;
            }

            // эту вершину можно удалить
            Node * x = p;
            p = p->m_Parent;
            if  (!p)
            {
                // делаем дерево пустым
                m_Root = nullptr;
            }
            else
            {
                const int c = (int)(unsigned char)x->m_Letter;
                p->m_Nodes[c] = nullptr;
            }
            delete x;
        }
        return p;
    }

    // Тестовая печать дерева, вызывается без параметров
    void Print(char * str = nullptr, Node * x = nullptr, int pos = 0) const;
    // Тестовая печать слов дерева, вызывается без параметров
    int PrintWords(char * str = nullptr, Node * x = nullptr, int pos = 0) const;

    // Получить имя ключа, универсально - с/без '\0' в конце
    bool GetKey(Handle h, char *p, int Size, bool bAdd0 = true, int *pSizeRequired = nullptr, int *pLen = nullptr) const noexcept
    {
        if  (h)
        {
            return h->GetKey(p, Size, bAdd0, pSizeRequired, pLen);
        }
        if  (Size > 0 && bAdd0)
        {
            *p = 0;
        }
        if  (pSizeRequired)
        {
            *pSizeRequired = 0; // or 1
        }
        if  (pLen)
        {
            *pLen = 0;
        }
        return false;
    }

    // Получить имя ключа в CMaaString
    CMaaString GetKey(Handle h) const
    {
        if  (h)
        {
            return h->GetKey();
        }
        CMaaString tmp;
        return tmp;
    }
};

#endif

#if 0
// Тестовая печать дерева, вызывается без параметров
template <> void CMaaTrie<int>::Print(char * str, Node * x, int pos) const
{
    if  (!x)
    {
        if  (str)
        {
            printf("%s !null\n", str);
            return;
        }
        printf("tree:\n"); fflush(stdout);
        static CMaaString buff(nullptr, 10 * 1024 + 1);
        str = (char *)(const char *)buff; *str = 0; pos = 0;
        x = m_Root;
        if  (!x)
        {
            printf("empty\n"); fflush(stdout);
            return;
        }
    }
    if  (x->m_bValue)
    {
        printf("%p %-15s v=%4d n=%4d  ", x, str, *(int *)x->m_Value, x->m_N);
    }
    else
    {
        printf("%p %-15s v=%4s n=%4d  ", x, str, "***", x->m_N);
    }
    for (int i = 0; i < x->m_N; i++)
    {
        printf("%c(%02x) ", x->m_Letters[i], (unsigned char)x->m_Letters[i]);
    }
    printf("\n");
    char * str2 = str + pos;
    if  (str2 - str2 < 10 * 1024)
    {
        for (int i = 0; i < x->m_N; i++)
        {
            str2[0] = x->m_Letters[i];
            str2[1] = 0;
            Print(str, x->m_Nodes[i], pos + 1);
            str2[0] = 0;
        }
    }
}

// Тестовая печать слов дерева, вызывается без параметров
template <> int CMaaTrie<int>::PrintWords(char * str, Node * x, int pos) const
{
    int V = 0;
    if  (!x)
    {
        if  (str)
        {
#ifdef TRIE10_DEBUG
            m_bDbg && printf("%s null\n", str);
#endif
            return -1;
        }
        //printf("tree:\n");
        static CMaaString buff(nullptr, 10 * 1024 + 1);
        str = (char *)(const char *)buff; *str = 0; pos = 0;
        x = m_Root;
        if  (!x)
        {
            //printf("empty\n");
            return V;
        }
    }
    if  (x->m_bValue)
    {
        V += *(int *)x->m_Value;
        printf("%05d %-15s\n", *(int *)x->m_Value, str);
    }
    char * str2 = str + pos;
    if  (str2 - str < 10 * 1024)
    {
        for (int i = 0; i < x->m_N; i++)
        {
            str2[0] = x->m_Letters[i];
            str2[1] = 0;
            V += PrintWords(str, x->m_Nodes[i], pos + 1);
            str2[0] = 0;
        }
    }
    return V;
}
#endif

#if 0

// Тестовая печать дерева, вызывается без параметров
template <> void CMaaTrie2<int, '\0', 256>::Print(char* str, Node* x, int pos) const
{
    if (!x)
    {
        if (str)
        {
            printf("%s !null\n", str);
            return;
        }
        printf("tree:\n"); fflush(stdout);
        static CMaaString buff(nullptr, 10 * 1024 + 1);
        str = (char*)(const char*)buff; *str = 0; pos = 0;
        x = m_Root;
        if (!x)
        {
            printf("empty\n"); fflush(stdout);
            return;
        }
    }
    if (x->m_bValue)
    {
        printf("%p %-15s v=%4d n=%4d  ", x, str, *(int*)x->m_Value, x->GetCount());
    }
    else
    {
        printf("%p %-15s v=%4s n=%4d  ", x, str, "***", x->GetCount());
    }
    //for (int i = 0; i < x->m_N; i++)
    //{
    //    printf("%c(%02x) ", x->m_Letters[i], (unsigned char)x->m_Letters[i]);
    //}
    for (int i = 0; i < 256; i++)
    {
        if (x->m_Nodes[i])
        {
            printf("%c(%02x) ", (char)(i + 0), (i + 0));
        }
    }
    printf("\n");
    char* str2 = str + pos;
    if (str2 - str2 < 10 * 1024)
    {
        /*
        for (int i = 0; i < x->m_N; i++)
        {
            str2[0] = x->m_Letters[i];
            str2[1] = 0;
            Print(str, x->m_Nodes[i], pos + 1);
            str2[0] = 0;
        }
        */
        for (int i = 0; i < 256; i++)
        {
            if (x->m_Nodes[i])
            {
                str2[0] = (char)(i + 0);
                str2[1] = 0;
                Print(str, x->m_Nodes[i], pos + 1);
                str2[0] = 0;
            }
        }
    }
}

// Тестовая печать слов дерева, вызывается без параметров
template <> int CMaaTrie2<int, '\0', 256>::PrintWords(char* str, Node* x, int pos) const
{
    int V = 0;
    if (!x)
    {
        if (str)
        {
#ifdef TRIE10_DEBUG
            m_bDbg&& printf("%s null\n", str);
#endif
            return -1;
        }
        //printf("tree:\n");
        static CMaaString buff(nullptr, 10 * 1024 + 1);
        str = (char*)(const char*)buff; *str = 0; pos = 0;
        x = m_Root;
        if (!x)
        {
            //printf("empty\n");
            return V;
        }
    }
    if (x->m_bValue)
    {
        V += *(int*)x->m_Value;
        printf("%05d %-15s\n", *(int*)x->m_Value, str);
    }
    char* str2 = str + pos;
    if (str2 - str < 10 * 1024)
    {
        /*
        for (int i = 0; i < x->m_N; i++)
        {
            str2[0] = x->m_Letters[i];
            str2[1] = 0;
            V += PrintWords(str, x->m_Nodes[i], pos + 1);
            str2[0] = 0;
        }
        */
        for (int i = 0; i < 256; i++)
        {
            if (x->m_Nodes[i])
            {
                str2[0] = (char)(i + 0);
                str2[1] = 0;
                V += PrintWords(str, x->m_Nodes[i], pos + 1);
                str2[0] = 0;
            }
        }
    }
    return V;
}

#endif


#if 0
// CMaaTrie<int> test function
int main_test_CMaaTrie(int argn, const char * args[])
{
    printf("Tests:\n");
    {
        printf("Test1: empty tree: "); fflush(stdout);
        CMaaTrie<int> a;
        printf("."); fflush(stdout);
        printf("%s", a.Find("a", 1) < 0 ? "." : " fail "); fflush(stdout);
        printf("%s", a.Find("abc", 1) < 0 ? "." : " fail "); fflush(stdout);
        CMaaTrie<int>::Handle h = a.FindHandle("ab");
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        printf("%s", !a.Remove("a") ? "." : " fail "); fflush(stdout);
        printf("."); fflush(stdout);
        h = a.FindGQ("ab");
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Next(h);
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.First();
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Next(h);
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Last();
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Prev(h);
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        printf("\n"); fflush(stdout);
        a.Print(); fflush(stdout);
        printf("~"); fflush(stdout);
    }
    printf(".\n"); fflush(stdout);
    printf("\n"); fflush(stdout);
    {
        printf("Test2: задание:\n");
        CMaaTrie<int> a;
        //a.SetDbg(true);
        /*
        a.Add("abc", 100);
        a.Add("abx", 10);
        a.Add("def", 2);
        a.Print();
        printf("%d ", a.Find("abc"));
        printf("%d ", a.Find("abx"));
        printf("%d ", a.Find("def"));
        printf("%d ", a.Find("klm"));
        printf("%d\n", a.Find("abd"));
        printf("%s\n", a.Remove("def") ? "true" : "false");
        printf("%d ", a.Find("abc"));
        printf("%d ", a.Find("def"));
        printf("%d ", a.Find("klm"));
        printf("%d\n", a.Find("abd"));
        a.Print();
        */
        const char * s[] = {"альфа", "бета", "гамма", "дельта", "эпсилон", "одна", "однаждыы", nullptr};
        printf("Find(not existed): %d\n", a.Find("бета"));
        printf("Remove(not existed): %s\n", a.Remove("бета") ? "true" : "false");
        int i;
        for (i = 0; s[i]; i++)
        {
            bool b = a.Add(s[i], i + 1);
            printf("Add %s %d %s  ", s[i], i + 1, b ? "true" : "false");
            printf("//Find(\"бета\") = %d\n", a.Find("бета"));
        }
        {
            CMaaString s = "однажды";
            int v = -1, len = -1, ilen = -1;
            a.MaxPath(s, s.Length(), &len, &ilen, &v);
            CMaaString p = s.Left(len);
            CMaaString ip = s.Left(ilen);
            printf("%s: %d %d ('%s', '%s') %d\n", (const char *)s, len, ilen, (const char *)p, (const char *)ip, v);
        }
        {
            CMaaString s = "однаждыыхх";
            int v = -1, len = -1, ilen = -1;
            a.MaxPath(s, s.Length(), &len, &ilen, &v);
            CMaaString p = s.Left(len);
            CMaaString ip = s.Left(ilen);
            printf("%s: %d %d ('%s', '%s') %d\n", (const char *)s, len, ilen, (const char *)p, (const char *)ip, v);
            //return 0;
        }
        if  (0)
        {
            a.Print();
            printf("LQ:\n");
            CMaaTrie<int>::Handle hh = a.FindGQ("бета");
            printf("%p\n", hh);
        }
        bool bEqual = false;
        //bEqual = true;
        printf("Test2: values for key %s \"бета\": ", bEqual ? ">=" : ">");
        for (CMaaTrie<int>::Handle h = a.FindGQ("бета", bEqual); h; h = a.Next(h))
        {
            //printf("%p %d\n", h, a.GetValue(h));
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
    }
    printf("\n");
    {
        printf("Test3: similar words: ");
        CMaaTrie<int> a;
        a.SetDbg(true);
        a.Add("zabc", 101);
        a.Add("zabcd", 102);
        a.Add("zabcde", 103);
        a.Add("zabcf", 104);
        a.Add("zabcfe", 105);
        a.Add("ax", 99);
        a.Remove("zabcf");
        printf("\n");
        a.Print();
        //gbDbgTrie10Nodes=true;
        for (CMaaTrie<int>::Handle h = a.FindGQ("zabc"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindGQ("za"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindGQ("AB"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindGQ("{"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindLQ("zabc"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindLQ("zabcd"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindLQ("zabce"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindLQ("zabcfg"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindLQ("Z"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie<int>::Handle h = a.FindLQ("{"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        a.SetDbg(false);
        //for (CMaaTrie<int>::iterator it = a.begin(); it; ++it)
        for (CMaaTrie<int>::iterator it = a.begin(); it != a.end(); ++it)
        {
            char key[1024 + 1];
            it.GetKey(key, (int)sizeof(key), true);
            printf("[%s]:%d ", key, it.data());
        }
        printf("\n");
        for (CMaaTrie<int>::iterator it = a.rbegin(); it != a.rend(); ++it)
        {
            char key[1024 + 1];
            it.GetKey(key, (int)sizeof(key), true);
            printf("[%s]:%d ", key, it.data());
        }
        printf("\n");
        for (CMaaTrie<int>::iterator it = a.begin(); it != a.end(); )
        {
            char key[1024 + 1];
            it.GetKey(key, (int)sizeof(key), true);
            printf("[%s]:%d ", key, it.data());
            CMaaTrie<int>::iterator r = it++;
            r.Remove();
        }
        printf("\n");
        for (CMaaTrie<int>::Handle p = a.First(); p; )
        {
            char key[1024 + 1];
            a.GetKey(p, key, (int)sizeof(key), true);
            printf("[%s] ", key);
            CMaaTrie<int>::Handle n = a.Next(p);
            a.Remove(p);
            p = n;
        }
        printf("\n");
        a.Print();
    }
    printf("\n");
    return 0;
}

bool gbDbgTrie10Nodes = false;
int main(int argn, const char * args[])
{
    return main_test_CMaaTrie(argn, args);
    //return main_test_CMaaTrie2(argn, args);
}
#endif

#if 0

// CMaaTrie2<int> test function
int main_test_CMaaTrie2(int argn, const char* args[])
{
    printf("Tests:\n");
    {
        printf("Test1: empty tree: "); fflush(stdout);
        CMaaTrie2<int> a;
        printf("."); fflush(stdout);
        printf("%s", a.Find("a", 1) < 0 ? "." : " fail "); fflush(stdout);
        printf("%s", a.Find("abc", 1) < 0 ? "." : " fail "); fflush(stdout);
        CMaaTrie2<int>::Handle h = a.FindHandle("ab");
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        printf("%s", !a.Remove("a") ? "." : " fail "); fflush(stdout);
        printf("."); fflush(stdout);
#if 1
        h = a.FindGQ("ab");
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Next(h);
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.First();
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Next(h);
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Last();
        printf("%s", !h ? "." : " fail "); fflush(stdout);
        h = a.Prev(h);
        printf("%s", !h ? "." : " fail "); fflush(stdout);
#endif
        printf("\n"); fflush(stdout);
        a.Print(); fflush(stdout);
        printf("~"); fflush(stdout);
    }
    printf(".\n"); fflush(stdout);
    printf("\n"); fflush(stdout);
    {
        printf("Test2: задание:\n");
        CMaaTrie2<int> a;
        //a.SetDbg(true);
        /*
        a.Add("abc", 100);
        a.Add("abx", 10);
        a.Add("def", 2);
        a.Print();
        printf("%d ", a.Find("abc"));
        printf("%d ", a.Find("abx"));
        printf("%d ", a.Find("def"));
        printf("%d ", a.Find("klm"));
        printf("%d\n", a.Find("abd"));
        printf("%s\n", a.Remove("def") ? "true" : "false");
        printf("%d ", a.Find("abc"));
        printf("%d ", a.Find("def"));
        printf("%d ", a.Find("klm"));
        printf("%d\n", a.Find("abd"));
        a.Print();
        */
        const char* s[] = { "альфа", "бета", "гамма", "дельта", "эпсилон", "одна", "однаждыы", nullptr };
        printf("Find(not existed): %d\n", a.Find("бета"));
        printf("Remove(not existed): %s\n", a.Remove("бета") ? "true" : "false");
        int i;
        for (i = 0; s[i]; i++)
        {
            const bool b = a.Add(s[i], i + 1);
            printf("Add %s %d %s  ", s[i], i + 1, b ? "true" : "false");
            printf("//Find(\"бета\") = %d\n", a.Find("бета"));
        }
        {
            CMaaString s = "однажды";
            int v = -1, len = -1, ilen = -1;
            a.MaxPath(s, s.Length(), &len, &ilen, &v);
            CMaaString p = s.Left(len);
            CMaaString ip = s.Left(ilen);
            printf("%s: %d %d ('%s', '%s') %d\n", (const char*)s, len, ilen, (const char*)p, (const char*)ip, v);
        }
        {
            CMaaString s = "однаждыыхх";
            int v = -1, len = -1, ilen = -1;
            a.MaxPath(s, s.Length(), &len, &ilen, &v);
            CMaaString p = s.Left(len);
            CMaaString ip = s.Left(ilen);
            printf("%s: %d %d ('%s', '%s') %d\n", (const char*)s, len, ilen, (const char*)p, (const char*)ip, v);
            //return 0;
        }
#if 1
        if (1)
        {
            a.Print();
            printf("LQ:\n");
            CMaaTrie2<int>::Handle hh = a.FindGQ("бета");
            printf("%p\n", hh);
            a.PrintWords();
        }
        bool bEqual = false;
        //bEqual = true;
        printf("Test2: values for key %s \"бета\": ", bEqual ? ">=" : ">");
        for (CMaaTrie2<int>::Handle h = a.FindGQ("бета", bEqual); h; h = a.Next(h))
        {
            //printf("%p %d\n", h, a.GetValue(h));
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
#endif
    }
    printf("\n");
    {
        printf("Test3: similar words: ");
        CMaaTrie2<int> a;
        //a.SetDbg(true);
        a.Add("zabc", 101);
        a.Add("zabcd", 102);
        a.Add("zabcde", 103);
        a.Add("zabcf", 104);
        a.Add("zabcfe", 105);
        a.Add("ax", 99);
        a.Remove("zabcf");
        printf("\n");
        a.Print();
        //gbDbgTrie10Nodes=true;
#if 1
        for (CMaaTrie2<int>::Handle h = a.FindGQ("zabc"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindGQ("za"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindGQ("AB"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindGQ("{"); h; h = a.Next(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindLQ("zabc"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindLQ("zabcd"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindLQ("zabce"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindLQ("zabcfg"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindLQ("Z"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle h = a.FindLQ("{"); h; h = a.Prev(h))
        {
            printf("%d ", a.GetValue(h));
        }
        printf("\n");
#endif
        //a.SetDbg(false);
        //for (CMaaTrie2<int>::iterator it = a.begin(); it; ++it)
        for (CMaaTrie2<int>::iterator it = a.begin(); it != a.end(); ++it)
        {
            char key[1024 + 1];
            it.GetKey(key, (int)sizeof(key), true);
            printf("[%s]:%d ", key, it.data());
        }
        printf("\n");
        for (CMaaTrie2<int>::iterator it = a.rbegin(); it != a.rend(); ++it)
        {
            char key[1024 + 1];
            it.GetKey(key, (int)sizeof(key), true);
            printf("[%s]:%d ", key, it.data());
        }
        printf("\n");
        for (CMaaTrie2<int>::iterator it = a.begin(); it != a.end(); )
        {
            char key[1024 + 1];
            it.GetKey(key, (int)sizeof(key), true);
            printf("[%s]:%d ", key, it.data());
            CMaaTrie2<int>::iterator r = it++;
            r.Remove();
        }
        printf("\n");
        for (CMaaTrie2<int>::Handle p = a.First(); p; )
        {
            char key[1024 + 1];
            a.GetKey(p, key, (int)sizeof(key), true);
            printf("[%s] ", key);
            CMaaTrie2<int>::Handle n = a.Next(p);
            a.Remove(p);
            p = n;
        }
        printf("\n");
        a.Print();
    }
    printf("\n");
    return 0;
}

int main(int argn, const char* args[])
{
    //return main_test_CMaaTrie(argn, args);
    return main_test_CMaaTrie2(argn, args);
}
#endif

#if 0

#define CMaaTrie_ver 1 // v.1 is the faster

#if CMaaTrie_ver == 1
#else
#define CMaaTrie CMaaTrie2
#endif

int main_pushkin(int argn, const char* args[])
{
    //main_test_CMaaTrie(argn, args);
    if (argn > 1)
    {
        CMaaTrie<int> a;
        CMaaUnivHash<CMaaString, int> ht;
        CMaaFile f(args[1], CMaaFile::eR_SrSw, false); // "pushkin_stihi.txt"
        CMaaString txt;
        CMaaString RussianAlphabet = "АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯабвгдежзийклмнопрстуфхцчшщъыьэюя";
        RussianAlphabet = Utf8ToAnsi(RussianAlphabet);
        CMaaString sp(NULL, 256);
        for (int ch = 0; ch < 256; ch++)
        {
            sp[ch] = RussianAlphabet.Find((char)ch) < 0 ? (char)ch : ' ';
        }
        //sp += " \t\r\n";
        CMaaString ut = "игр";
        __utf8_printf("%S ", &ut);
        CMaaString t = Utf8ToAnsi(ut);
        int t0 = 0;// -1;
        CHrtMultiTimer tmr;
        tmr.Start();
        while (txt.IsNotEmpty() || f.IsOpen())
        {
            if (txt.Length() < 1 * 1024 && f.IsOpen())
            {
                txt += f.Read(4 * 1024);
                if (f.IsEOF())
                {
                    f.Close();
                }
            }
            CMaaString w = txt.GetWord(true, true, sp).ToLower(1251);
            CMaaString u = UnicodeToUtf8(AnsiToUnicode(w));
            int v = 0;
            a.Find(w, w.Length(), &v);
            v++;
            if (v <= 0)
            {
                __utf8_printf("%-15S == %d\n", &u, v);
            }
            a.Add(w, w.Length(), v);
            int v2 = a.Find(w, w.Length());
            if (v2 != v)
            {
                __utf8_printf("%-15S %d <> %d\n", &u, v2, v);
            }
            else
            {
                //__utf8_printf("%-15S %d\n", &u, v2);
            }
            int vt = 0;
            ht.Find(w, &vt);
            vt++;
            ht.AddOver(w, vt);
            if (vt != v)
            {
                __utf8_printf("%-15S %d <> %d(ht)\n", &u, v, vt);
            }
            if (w == t)
            {
                if (!++t0)
                {
                    t0++;
                }
            }
            v = a.Find(t, t.Length());
            if (t0 != v)
            {
                __utf8_printf("after %S #%d: %S = %d <> %d\n", &u, v2, &ut, v, t0);
            }
        }
        tmr.Stop("Add/Find");
        int V = a.PrintWords();
        fflush(stdout);
        __utf8_printf("   %d\n", V);

        V = 0;
#if CMaaTrie_ver == 1
        const char* p_min_1 = "\x80";
        const char* p_max_12 = "\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f";
#else
        const char* p_min_1 = "\x00";
        const char* p_max_12 = "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff";
#endif
        const int p_max_len = (int)strlen(p_max_12);

        int N = a.Find(p_min_1, 1, &V) ? 1 : 0;
        //gbDbgTrie10Nodes = true;
        CMaaTrie<int>::Handle h0 = NULL;
        tmr.Start();
        for (CMaaTrie<int>::Handle h = a.FindGQ(p_min_1, 1); h; h = a.Next(h))
        {
            if (!h0)
            {
                h0 = h;
                __utf8_printf("%p ", h);
            }
            N++;
            V += a.GetValue(h);
            //__utf8_printf("%d\n", N);
        }
        tmr.Stop("Next");
        __utf8_printf("%d %d >\n", N, V);

        V = 0;
        N = a.Find(p_max_12, p_max_len, &V) ? 1 : 0;
        //gbDbgTrie10Nodes = true;
        h0 = NULL;
        tmr.Start();
        for (CMaaTrie<int>::Handle h = a.FindLQ(p_max_12, p_max_len); h; h = a.Prev(h))
        {
            if (!h0)
            {
                h0 = h;
                __utf8_printf("%p ", h);
            }
            N++;
            V += a.GetValue(h);
            //__utf8_printf("%d\n", N);
        }
        tmr.Stop("Prev");
        __utf8_printf("%d %d <\n", N, V);
        //__utf8_printf("%d\n", a.Find(t, t.Length()));

        CMaaString res = tmr.GetResult("CMaaTrie<int>:\n");
        __utf8_printf("%S\n", &res);

        V = 0; N = 0;
        CMaaUnivHash<CMaaString, int>::iterator it(ht);
        for (; it; ++it)
        {
            N++;
            V += it.data();
        }
        __utf8_printf("%d %d ht\n", N, V);

        h0 = a.First(); __utf8_printf("%p ", h0);
        h0 = a.Last(); __utf8_printf("%p\n", h0);

        CMaaPtrAE<CMaaTrie<int>::Handle> m(N);
        int idx = 0;
        for (CMaaTrie<int>::Handle h = a.First(); h; h = a.Next(h))
        {
            m[idx] = h;
            a.SetValue(h, idx);
            idx++;
        }
        CMaaString w1, w2;
        for (CMaaTrie<int>::Handle h = a.Last(); h; h = a.Prev(h))
        {
            --idx;
            if (m[idx] != h)
            {
                __utf8_printf("%4d %p:%d <> %p:%d\n", idx, h, a.GetValue(h), (CMaaTrie<int>::Handle)m[idx], a.GetValue(m[idx]));
            }
            char k[256];
            *k = 0;
            a.GetKey(h, k, 256);
            w2 = k;
            if (w1 < w2)
            {
                __utf8_printf("%4d %p %4d %S < %S\n", idx, h, a.GetValue(h), &w1, &w2);
            }
            w1 = w2;
        }

        return 0;
    }
    return 0;
}

#endif